/**
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 进一步性能优化.先找到山峰,然后从左开始到山峰,再从右往山峰.避免当前从山峰往右时重复的遍历.
 */
class Solution {

    public static void main(String[] args) {
        int[] height = new int[]{5,3,2,6};
        new Solution().trap(height);
    }

    public int trap(int[] height) {
        int[] waterLine = new int[height.length];
        makeWaterLine(height, waterLine);
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            int water = waterLine[i] - height[i];
            if (water <= 0) {
                continue;
            }
            sum += water;
        }

        for (int i = 0; i < height.length; i++) {
            System.out.print(height[i]);
        }
        System.out.println();
        for (int i = 0; i < height.length; i++) {
            System.out.print(waterLine[i]);
        }
        System.out.println();
        System.out.println(sum);

        return sum;
    }

    public void makeWaterLine(int[] pillar, int[] waterLine) {
        int curIndex = 0;

        while (true) {
            int curValue = pillar[curIndex];
            if (curIndex == (pillar.length - 1)) {
                waterLine[curIndex] = pillar[curIndex];
                break;
            }

            int rightIndex = curIndex + 1;
            int maxValue = -1;
            int maxIndex = -1;
            while (rightIndex < pillar.length) {
                int rightValue = pillar[rightIndex];
                if (rightValue >= curValue) {
                    setWaterLine(waterLine, curIndex, rightIndex - 1, curValue);
                    curIndex = rightIndex;
                    curValue = pillar[curIndex];
                    rightIndex++;
                    maxValue = -1;
                    maxIndex = -1;
                } else {
                    if (maxValue <= rightValue) {
                        maxValue = rightValue;
                        maxIndex = rightIndex;
                    }
                    rightIndex++;
                }
            }

            if (maxIndex < 0) {
                waterLine[curIndex] = pillar[curIndex];
            } else {
                setWaterLine(waterLine, curIndex, maxIndex - 1, maxValue);
                curIndex = maxIndex;
            }
        }


    }

    public void setWaterLine(int[] waterLine, int start, int end, int line) {
        for (int i = start; i <= end; i++) {
            waterLine[i] = line;
        }
    }

}